#include <gtest/gtest.h>
#include "common.h"
#include <algorithm>

using namespace ::std;

class Solution {
public:
    int leastInterval(vector<char>& tasks, int n);
};

// 最先安排数量最多的任务，并且在安排的过程中尽可能的保持任务的多样性
// 有对数组中数据的存取操作，就需要在使用之前考虑是否可能会越界
// LeetCode使用了AddressSanitizer检查是否存在内存非法访问
// ==42==ERROR: AddressSanitizer: heap-buffer-overflow on address 0x60b000001078 ...
int Solution::leastInterval(vector<char>& tasks, int n) {
    int taskNum = tasks.size(), result = 0;
    if(0 == n) return taskNum;
    vector<int> map('Z' - 'A' + 1, 0);
    for(char c : tasks) map[c - 'A']++;
    while(taskNum > 0) {
        int sameMaxNumTask = 1, leftInterval = 0, balance = 1;

        // 先按任务数量的多少从大到小排序
        sort(map.begin(), map.end(), greater<int>());

        // 统计最大数量的任务数，每轮次每个任务只安排一次
        while(sameMaxNumTask < 26 && map[sameMaxNumTask] == map[sameMaxNumTask - 1]) sameMaxNumTask++;

        // scheduleMaxNumTask(map, sameMaxNumTask, n, balance, leftInterval, taskNum, result);
        int multiple = 0, complement = 0;
        multiple = sameMaxNumTask / (n + 1);
        if((complement = sameMaxNumTask % (n + 1)) != 0) {
            result += (multiple + 1) * balance * (n + 1);
            leftInterval = (n + 1 - complement) * balance;
        } else result += multiple * balance * (n + 1);
        
        // fillLeftInterval(map, leftInterval, sameMaxNumTask, taskNum, result);
        for(int i = sameMaxNumTask; i < 26 && map[i] > 0 && leftInterval > 0; taskNum--, map[i++]--, leftInterval--) ;

        taskNum -= sameMaxNumTask * balance;
        while(sameMaxNumTask > 0) map[--sameMaxNumTask] -= balance;
        
        if(leftInterval > 0 && (multiple > 0 || taskNum == 0)) result -= min((n + 1) - complement, leftInterval);
    }
    return result;
}

// class Solution {
// public:
//     int leastInterval(vector<char>& tasks, int n) {
//         int len = tasks.size();
//         vector<int> buckets(26);
//         for (auto& ch : tasks) buckets[ch-'A']++;
//         sort(buckets.begin(), buckets.end(), [](int& a, int& b) {return a>b;});
//         int cnt = 1;
//         while (cnt <26 && buckets[cnt] == buckets[0]) cnt++;
//         return max(len, cnt + (buckets[0] - 1) * (n+1));
//     }
// };

class LeastIntervalCheck : public ::testing::Test {
public:
	class Solution solution;
};

TEST_F(LeastIntervalCheck, testLeastInterval_1) {
    vector<char> tasks = {'A','A','A','B','B','B'};
    int n = 2;
    EXPECT_TRUE(8 == solution.leastInterval(tasks, n));
}

TEST_F(LeastIntervalCheck, testLeastInterval_2) {
    vector<char> tasks = {'A','A','A','B','B','B','C','C','D','D'};
    int n = 2;
    EXPECT_TRUE(10 == solution.leastInterval(tasks, n));
}

TEST_F(LeastIntervalCheck, testLeastInterval_3) {
    vector<char> tasks = {'A','A','B','B','C','C','D'};
    int n = 1;
    EXPECT_TRUE(7 == solution.leastInterval(tasks, n));
}

TEST_F(LeastIntervalCheck, testLeastInterval_4) {
    vector<char> tasks = {'A','A','A','A','A','A','B','C','D','E','F','G'};
    int n = 2;
    EXPECT_TRUE(16 == solution.leastInterval(tasks, n));
}

TEST_F(LeastIntervalCheck, testLeastInterval_5) {
    vector<char> tasks = {'A','B','C','D','E','A','B','C','D','E'};
    int n = 4;
    EXPECT_TRUE(10 == solution.leastInterval(tasks, n));
}

TEST_F(LeastIntervalCheck, testLeastInterval_6) {
    vector<char> tasks = {'A','A','A','B','B','B','C','C','C','D','D','E'};
    int n = 2;
    EXPECT_TRUE(12 == solution.leastInterval(tasks, n));
}

TEST_F(LeastIntervalCheck, testLeastInterval_7) {
    vector<char> tasks = {'A','A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z'};
    int n = 29;
    EXPECT_TRUE(31 == solution.leastInterval(tasks, n));
}

TEST_F(LeastIntervalCheck, testLeastInterval_8) {
    vector<char> tasks = {'A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z','A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z'};
    int n = 2;
    EXPECT_TRUE(52 == solution.leastInterval(tasks, n));
}

TEST_F(LeastIntervalCheck, testLeastInterval_9) {
    vector<char> tasks = {'A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z'};
    int n = 2;
    EXPECT_TRUE(51 == solution.leastInterval(tasks, n));
}

int main() {
	::testing::InitGoogleTest();
	return RUN_ALL_TESTS();
}

// // 最先安排数量最多的任务，并且在安排的过程中尽可能的保持任务的多样性
// int Solution::leastInterval(vector<char>& tasks, int n) {
//     int taskNum = tasks.size(), result = 0;
//     if(0 == n) return taskNum;
//     vector<int> map('Z' - 'A' + 1, 0);
//     for(char c : tasks) map[c - 'A']++;
//     while(taskNum > 0) {
//         int sameMaxNumTask = 1, leftInterval = 0, balance = 0;

//         // 先按任务数量的多少从大到小排序
//         sort(map.begin(), map.end(), greater<int>());

//         // 统计最大数量的任务数，并计算比第二多数量任务多出来的差值
//         while(sameMaxNumTask < 26 && map[sameMaxNumTask] == map[sameMaxNumTask - 1]) sameMaxNumTask++;
//         // if(sameMaxNumTask < 26) balance = map[sameMaxNumTask - 1] - map[sameMaxNumTask];
//         // else balance = map[0];
//         balance = 1;

//         // scheduleMaxNumTask(map, sameMaxNumTask, n, balance, leftInterval, taskNum, result);
//         int multiple = 0, complement = 0;
//         multiple = sameMaxNumTask / (n + 1);
//         if((complement = sameMaxNumTask % (n + 1)) != 0) {
//             result += multiple * balance * (n + 1) + balance * (n + 1);
//             leftInterval = (n + 1 - complement) * balance;
//         } else result += multiple * balance * (n + 1);
        
//         // fillLeftInterval(map, leftInterval, sameMaxNumTask, taskNum, result);
//         // 此处有几处漏洞，但LeetCode的用例库检不出来，< 26 可能会导致死循环
//         while(sameMaxNumTask < 26 && leftInterval > 0 && map[sameMaxNumTask] > 0) {
//             for(int i = sameMaxNumTask; i < 25 && leftInterval > 0; ) {
//                 if(map[i + 1] > map[i]) i++;
//                 taskNum--;
//                 map[i]--;
//                 leftInterval--;
//                 if(i < 25 &&  map[i] == 0 && map[i + 1] == 0) break;
//             }
//         }

//         taskNum -= sameMaxNumTask * balance;
//         while(sameMaxNumTask > 0) map[--sameMaxNumTask] -= balance;

//         if(leftInterval > 0 && (multiple > 0 || taskNum == 0)) result -= min((n + 1) - complement, leftInterval);

//     }
//     return result;
// }